﻿using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Timtopia.DGMLPosterView;

namespace UnitTestProject1
{
    using CharNode = Timtopia.DGMLPosterView.PowerGraphDecomposition.TreeNode<char?>;
    using Microsoft.VisualStudio.GraphModel;

    [TestClass]
    public class PowerGraphDecompositionTests
    {
        [TestMethod]
        public void LeastCommonAncestors()
        {
            var a = new CharNode('a');
            var b = new CharNode('b');
            var c = new CharNode('c');
            var d = new CharNode('d');
            var e = new CharNode('e');
            var f = new CharNode('f');
            var g = new CharNode('g');

            a.AddChildren(b, c);
            b.AddChildren(d, e);
            e.AddChildren(f, g);

            Assert.AreEqual("(c,((g,f)e,d)b)a", a.ToString());

            CharNode firstAncestor, secondAncestor;
            var lca = d.LeastCommonAncestor(g, out firstAncestor, out secondAncestor);
            Assert.AreEqual(b, lca);
            Assert.AreEqual(d, firstAncestor);
            Assert.AreEqual(e, secondAncestor);

            lca = f.LeastCommonAncestor(g, out firstAncestor, out secondAncestor);
            Assert.AreEqual(e, lca);
            Assert.AreEqual(f, firstAncestor);
            Assert.AreEqual(g, secondAncestor);

            lca = a.LeastCommonAncestor(a, out firstAncestor, out secondAncestor);
            Assert.AreEqual(a, lca);
            Assert.AreEqual(a, firstAncestor);
            Assert.AreEqual(a, secondAncestor);

            lca = b.LeastCommonAncestor(e, out firstAncestor, out secondAncestor);
            Assert.AreEqual(b, lca);
            Assert.AreEqual(b, firstAncestor);
            Assert.AreEqual(b, secondAncestor);
        }
        
        [TestMethod]
        public void PairCluster()
        {
            char?[] nodes = { 'a', 'b', 'c', 'd', 'e', 'f', 'g' };
            var tree = PowerGraphDecomposition.PairCluster(nodes, new[] {
                CharPair('f','g'),
                CharPair('d','e'),
                CharPair('c','d'),
                CharPair('d','f'),
                CharPair('a','c'),
                CharPair('b','c'),
                CharPair('e','g'),
            });
            Assert.AreEqual(2, tree.Children.Count);
            Assert.AreEqual("((((g,f),((e,d),c)),a),b)", tree.ToString());
        }

        Tuple<char?, char?> CharPair(char? a, char? b)
        {
            return Tuple.Create(a, b);
        }

        [TestMethod]
        public void NodeSimilarities()
        {
            var t = new TestGraph();

            Dictionary<GraphNode, PowerGraphDecomposition.Neighbours<GraphNode>> neighbours = PowerGraphDecomposition.GetNeighbours(t.V);

            var similarities = PowerGraphDecomposition.ComputeNodeSimilarities(t.V, neighbours)
                .OrderBy(s => s.Item2.Id)
                .OrderBy(s => s.Item3.Id)
                .OrderByDescending(s => s.Item1);

            var expected = new[] {
                Tuple.Create(1d, t.a, t.b),
                Tuple.Create(1d, t.c, t.d),
                Tuple.Create(0.667, t.c, t.e),
                Tuple.Create(0.667, t.d, t.e),
                Tuple.Create(0.2, t.a, t.c),
                Tuple.Create(0.2, t.b, t.c),
            };

            foreach (var s in similarities.Zip(expected, (u, v) => new { actual = u, expect = v }))
            {
                Assert.AreEqual(s.expect.Item2, s.actual.Item2);
                Assert.AreEqual(s.expect.Item3, s.actual.Item3);
                Assert.AreEqual(s.expect.Item1, s.actual.Item1, 0.01);
            }

            var tree = PowerGraphDecomposition.PairCluster(t.V, from s in similarities select Tuple.Create(s.Item2, s.Item3));
            ValidateTree(tree);

            Assert.AreEqual("((e,(d,c)),(b,a))", tree.ToString().Replace("{}", "").Replace(" ", "").Replace("\"", ""));
        }

        private static void ValidateTree(PowerGraphDecomposition.TreeNode<GraphNode> root)
        {
            var internalNodes = root.InternalNodes;
            var leaves = root.Leaves;
            foreach (var v in internalNodes)
            {
                if (v.Parent == null)
                {
                    Assert.AreSame(v, root, "only the root can have no parent");
                }
                int childrenLeafCount = 0;
                int leafCount = v.Leaves.Count();
                Assert.AreEqual(2, v.Children.Count, "tree should be binary because it was generated by pair-wise matching");
                foreach (var c in v.Children)
                {
                    childrenLeafCount += c.Leaves.Count();
                }
                Assert.AreEqual(leafCount, childrenLeafCount, "the number of leaves below an internal node should be the same as the sum of leaves below each of its children");
            }

            // because it's binary the following should be true
            Assert.AreEqual(internalNodes.Count() + 1, leaves.Count(), "because the tree is binary we expect |leaves| - |internalNodes| == 1");
        }

        [TestMethod]
        public void CandidateSet()
        {
            var t = new TestGraph();
            var s = new [] {t.a, t.b};
            var neighbours = PowerGraphDecomposition.GetNeighbours(t.V);
            var ab = new PowerGraphDecomposition.CandidateSet(s, neighbours);
            Assert.IsTrue(ab.OutgoingCommon.SetEquals(new[] { t.c, t.d, t.e }));
            Assert.AreEqual(3, ab.CostDelta);
            var set = ab.Create(t.g, neighbours, "Group1");
            Assert.IsTrue(ab.OutgoingCommon.SetEquals(neighbours[set].Outgoing));
        }

        [TestMethod]
        public void PowerGraphDecompositionTest()
        {
            var t = new TestGraph();
            PowerGraphDecomposition.Apply(t.g);

            Assert.AreEqual(2, t.g.AllGroups.Count());
        }

        private class TestGraph
        {
            public Graph g;
            public GraphNode a, b, c, d, e;
            public IList<GraphNode> V;
            public TestGraph()
            {
                g = new Graph();
                a = g.Nodes.GetOrCreate("a");
                b = g.Nodes.GetOrCreate("b");
                c = g.Nodes.GetOrCreate("c");
                d = g.Nodes.GetOrCreate("d");
                e = g.Nodes.GetOrCreate("e");

                var ac = g.Links.GetOrCreate("a", "c");
                var ad = g.Links.GetOrCreate("a", "d");
                var ae = g.Links.GetOrCreate("a", "e");
                var bc = g.Links.GetOrCreate("b", "c");
                var bd = g.Links.GetOrCreate("b", "d");
                var be = g.Links.GetOrCreate("b", "e");
                var cd = g.Links.GetOrCreate("c", "d");

                V = g.Nodes.ToArray();
            }
        }
    }
}
